package 每日一题OJ;

/**
 * @author shy_black
 * @date 2019/8/19 21:21
 * @Description:
 */
public class _215_数组中的第K个最大元素 {
    static int kk;
    public int findKthLargest(int[] arr, int k) {
        kk = arr.length - k;
        quickSort(arr,0,arr.length-1);
        return arr[kk];
    }
    private static void quickSort(int[] arr, int l,int r) {

        int mid = part(arr,l,r);
        if(l < r) {
            if(kk == mid)
                return ;
            if(kk < mid)
                quickSort(arr,l,mid-1);
            if(kk > mid)
                quickSort(arr,mid+1,r);
        }
    }
    private static int part(int[] arr ,int l,int r) {
        if(l > r)
            return -1;
        int key = r;
        while(l < r){
            while(l < r && arr[r] > arr[key])
                r--;
            while(l < r && arr[l] <= arr[key])
                l++;
            swap(arr,l,r);
        }
        swap(arr,l,key);
        return l;
    }

    private static void swap(int[] arr,int l,int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

}